A circuit implementation for a substitutional compressor which uses a history buffer for storing the previous pixels and comparators for comparing the current pixel to every previous pixel in the history buffer.
A substitutional compressor functions by replacing blocks of pixels with shorter references to earlier occurrences of identical blocks of pixels. For a numerical example, in the previous paragraph, the second occurrence of the words "history buffer" is repeated 126 spaces after the first occurrence in the word string (the "displacement"), and is a collection of 14 characters, counting the space between words, (the "length"). Thus, the second occurrence of "history buffer" can be replaced with the code word "126, 14".
The algorithm always looks for the longest possible match. Thus, after finding a match for "history buffe", it will look for "history buffer" which it will find, and then "history buffer." (with a period after it) which it will not find (the previous occurrence had a following space). Thus, "history buffer" will be the longest possible match.
The detailed algorithm can be found in a number of publications such as Edward R. Fiala and Daniel H. Greene, "Data Compression with Finite Windows" Communication of the ACM, April 1989, Volume 32, Number 4, 490-505. Many other references are also given by this paper.
A typical history buffer would be 4K pixels long and the longest permissible match can be as much as 256 pixels, at up to eight bits per pixel. The algorithm can be implemented in software, but hardware would be preferred because of its higher speed. Content Addressable Memories (CAM) could be used. For example, 8-bit pixels could be loaded into 4K CAMs, and the current pixel could be compared to each. The next cycle would be to replace the oldest pixel with the current pixel, and use a new pixel for the next comparison. However, it would be inefficient to develop CAM hardware to perform this function. Using CAM's would require massive storage space and involve operation steps that are difficult to pipeline or parallel in hardware. The resulting device would be large and complex and its operation speed would not meet the requirements of high performance products. A completely new approach needs to be taken to resolve this problem.